/**
 * Definition for a QuadTree node.
 * type Node struct {
 *     Val bool
 *     IsLeaf bool
 *     TopLeft *Node
 *     TopRight *Node
 *     BottomLeft *Node
 *     BottomRight *Node
 * }
 */

func construct(grid [][]int) *Node {
    row, col := len(grid), len(grid[0])
    return dfs(grid, 0, 0, row, col)
}

func dfs(grid [][]int, r0 int, c0 int, r1 int, c1 int) *Node {
    same := true
    for i := r0; i < r1; i++ {
        for j := c0; j < c1; j++ {
            if grid[i][j] != grid[r0][c0] {
                same = false
                break
            }
        }
        if !same {
            break
        }
    }

    if same {
        return &Node{Val: grid[r0][c0] == 1, IsLeaf: true}
    }

    topLeft := dfs(grid, r0, c0, (r0 + r1) / 2, (c0 + c1) / 2)
    topRight := dfs(grid, r0, (c0 + c1) / 2, (r0 + r1)/ 2, c1)
    bottomLeft := dfs(grid, (r0 + r1) / 2, c0, r1, (c0 + c1) / 2)
    bottomRight := dfs(grid, (r0 + r1) / 2, (c0 + c1) / 2, r1, c1)

    return &Node{Val: true, TopLeft: topLeft, TopRight: topRight, BottomLeft: bottomLeft, BottomRight: bottomRight}
}